package cn.edu.cdu.argorithm.impl;

import cn.edu.cdu.argorithm.ILinkedListCycleII;
import cn.edu.cdu.argorithm.common.ListNode;

import java.util.HashSet;
import java.util.Set;

public class LinkedListCycleII {
    public static class Solution1 implements ILinkedListCycleII {
        @Override
        public ListNode detectCycle(ListNode head) {
            Set<ListNode> cache = new HashSet<>();
            while (head != null && head.next != null) {
                if(!cache.add(head)) {
                    return head;
                }
                head = head.next;
            }
            return null;
        }
    }

    public static class Solution2 implements ILinkedListCycleII{
        @Override
        public ListNode detectCycle(ListNode head) {
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast) {
                    slow = head;
                    while (slow != fast) {
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return fast;
                }
            }
            return null;
        }
    }
}
